public class test40_11_18 {
    /*74. 搜索二维矩阵
中等
相关标签
相关企业

给你一个满足下述两条属性的 m x n 整数矩阵：

    每行中的整数从左到右按非严格递增顺序排列。
    每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。



示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
*/
    public static void main(String[] args) {
         int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        System.out.println(searchMatrix(matrix,24));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0)
            return false;
        int head=0,tail=matrix.length-1,left=0,right=matrix[0].length-1,mid=0;
        while(head<tail){
            mid=head+(tail-head)/2;
            if(matrix[mid][matrix[0].length-1]>=target)
                tail=mid;
            else
                head=mid+1;
        }
        while(left<right){
            mid=left+(right-left)/2;
            if(matrix[head][mid]>=target)
                right=mid;
            else
                left=mid+1;
        }
        if(matrix[head][left]==target||matrix[head][right]==target)
            return true;
        return false;
    }
}
